package Array_and_String;
/*
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/array-and-string/cxqdh/
 */

import java.util.Arrays;

public class _12搜索插入位置 {
    public static void main(String[] args) {

        int[] n = {1,3,5,6};

        System.out.println(searchInsert(n, 5));

        System.out.println(searchInsert2(n, 5));

    }

    //方法一:二分查找
    public static int searchInsert(int[] nums, int target) {
        int i = Arrays.binarySearch(nums, target);
        if (i < 0)
            return -i - 1;
        else
            return i;
    }

    //方法二:二分查找
    public static int searchInsert2(int[] nums, int target) {
        //创建左右指针
        int left = 0, right = nums.length - 1;

        while (left <= right){
            //计算出中间index -- mid
            int mid = ((left + right) >> 1);

            //比较mid值与target值的大小
            if (nums[mid] > target){
                //如果mid大
                right = mid - 1;
            }else if (nums[mid] < target){
                //如果mid小
                left = mid + 1;
            }else{
                return mid;
            }
        }

        //循环完成未找到,返回应插入的index
        return left;
    }
}
